import java.util.ArrayList;

/**
 * This class actual do the traverse the paths
 * based on the algorithm 
 * @author ldong
 *
 */
public class GraphTraverser 
{
     private boolean visited = true;
     private boolean unvisited = false;
     private ArrayList<Record> recordList;
     private EdgeList edgeList;

     /**
      * Constructor
      * @param ds
      * @param graph
      * @param startName
      */
     public GraphTraverser(DataStructure<Record> ds, AdjacencyList graph,
		      String startName)
     {
    	 edgeList = new EdgeList();
    	 recordList = new ArrayList<Record>();
		 traverse(ds,graph,startName);
     }
     
     /**
      * Traverse the paths 
      * @param ds
      * @param graph
      * @param startName
      * @return
      */
     public ArrayList<Record> traverse(DataStructure<Record> ds, AdjacencyList graph,
    		      String startName)
     {
    	 // make an arrayList or records
    	 recordList = new ArrayList<Record>();
    	 
        // mark all vertices as unvisited  
        graph.resetFlag(unvisited);
        
	    // pick a startName as starting vertex 
        Vertex startVertex = graph.getAdjacentStringVertextable().get(startName);
    	Record rec = new Record(startVertex);
    	
    	ds.add(rec);  // adds to record
    	
		while(!ds.isEmpty())
	    {
	    	Record currRec = ds.remove();
	    	Vertex lastVertex = currRec.getVertex(currRec.size()-1);
	    	
			 if(!lastVertex.isVisited())
			 {
				 lastVertex.setMark(visited);

//				 for(Vertex v : lastVertex.getVertexSet())
				 for(Vertex v : lastVertex.getVertexList())
				 {
			    	 Record newRec = new Record(currRec, v);
			    	 ds.add(newRec);
			    	 
				 }//end of for loop

				 // add current rec to the list
				 recordList.add(currRec);
				 
			 }// end of if
    	 }// end of while loop
        return recordList;
     }
     
     
     /**
      * Print the outputs as edges
      */
 	public void printEdge()
    {
		int sum = 0;
		for(int i= 1; i<recordList.size() ;i++)
		{
			Edge e = new Edge(recordList.get(i).getVertex(recordList.get(i).size()-1),
					recordList.get(i).getVertex(recordList.get(i).size()-2),
					recordList.get(i).getLastEdgeWeight() );
			
			sum += recordList.get(i).getLastEdgeWeight();
			
			edgeList.addEdge2List(e);
		}
		
		System.out.print(edgeList);
		System.out.println("Total: "+sum);
		
    }
    /**
     * Print the outputs as paths
     */
     public void printPaths()
     {
    	 for(int i = 0; i < recordList.size(); i++)
    	   System.out.println(recordList.get(i).toString());
     }
}
